#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 * parser the expression such as "(a+(b*c))+(((d*e)+f)*g)"
 * 2020-1-28
 * thelxz
 *
 */

struct node {
    char node_name;
    struct node *left;
    struct node *right;
};

int split_element(char *expr, int size) {

    int i;
    int cnt;
retry:
    cnt = 0;
    for (i = 0; i < size; i++) {
        if (expr[i] == '(')
            cnt++;
        if (expr[i] == ')')
            cnt--;
        if (cnt == 0) {
            return i+1;
        }
    }
}

int has_out_brace(char * expr, int size){
    int i;
    int cnt = 0;
    if (expr[0] != '('){
        return 0;
    }
    for (i = 0; i < size; i++) {
        if (expr[i] == '(')
            cnt++;
        if (expr[i] == ')')
            cnt--;
        if ((cnt == 0) && (i!=size-1)){
            return 0;
        }
    }
    return 1;

}

/*
 * 带括号的中缀表达式转换成表达式树
 * 因为括号的原因不需要考虑优先级，实际考虑优先级的情况下，更好的策略是中缀表达式先转成后缀表达式，再处理
 * a+(b*c) --> loc = 1
 * left =  str[0],size=loc
 * opera = str[loc] = '+'
 * right = str+loc+1, size=size-loc-1
 */
struct node *parser_expr(char *expr, int size) {
    struct node *cur_node = (struct node *) malloc(sizeof(struct node));
    if(has_out_brace(expr, size)){
        expr++;
        size -= 2;
    }
    if (size == 1) {
        cur_node->left = NULL;
        cur_node->right = NULL;
        cur_node->node_name = expr[0];
    } else {
        int loc = split_element(expr, size);
        int str1_len = loc;
        int str2_len = size - loc - 1;
        cur_node->node_name = expr[loc];
        cur_node->left = parser_expr(expr, str1_len);
        cur_node->right = parser_expr(expr + loc + 1, str2_len);
    }
    return cur_node;
}

struct expr{
    char str[100];
};


struct expr to_prefix(struct node *expr_tree) {
    struct expr result;
    result.str[0] = '\0';
    if (expr_tree->left == NULL){
        result.str[0] = expr_tree->node_name;
        result.str[1] = '\0';
    }else{
        int len = strlen(result.str);
        result.str[len] = expr_tree->node_name;
        result.str[len+1] = '\0';
        strcat(result.str, to_prefix(expr_tree->left).str);
        strcat(result.str, to_prefix(expr_tree->right).str);
    }
    return result;
}

struct expr to_infix(struct node *expr_tree) {
    struct expr result;
    result.str[0] = '\0';
    if (expr_tree->left == NULL){
        result.str[0] = expr_tree->node_name;
        result.str[1] = '\0';
    }else{
        strcat(result.str, "(");
        strcat(result.str, to_infix(expr_tree->left).str);
        int len = strlen(result.str);
        result.str[len] = expr_tree->node_name;
        result.str[len+1] = '\0';
        strcat(result.str, to_infix(expr_tree->right).str);
        strcat(result.str, ")");
    }
    return result;
}

// c can't return array, but can return struct
struct expr to_postfix(struct node *expr_tree) {
    struct expr result;
    result.str[0] = '\0';
    if (expr_tree->left == NULL){
        result.str[0] = expr_tree->node_name;
        result.str[1] = '\0';
    }else{
        strcat(result.str, to_postfix(expr_tree->left).str);
        strcat(result.str, to_postfix(expr_tree->right).str);
        int len = strlen(result.str);
        result.str[len] = expr_tree->node_name;
        result.str[len+1] = '\0';
    }
    return result;
}

int main() {
    char expr[] = "(a+(b*c))+(((d*e)+f)*g)";
    struct node * expr_tree = parser_expr(expr,strlen(expr));
    struct expr result;
    result = to_prefix(expr_tree);
    printf("Prefix:  %s\n", result.str);
    result = to_infix(expr_tree);
    printf("Infix:   %s\n", result.str);
    result = to_postfix(expr_tree);
    printf("Postfix: %s\n", result.str);

    int number = 100;
    printf("Hello, World! %d\n", number);
    return 0;
}
